package com.suanfa.collect;

import com.alibaba.fastjson.JSON;

import java.util.*;

/**
 * 集合有重复元素，求集合所有子集
 */
public class SubSetsRepeat {

    public static void main1(String[] args) {
        List<List<Integer>> ans = new ArrayList<>();

        List<Integer> list = new ArrayList<>();

        int[] arr = {1,2,3};
        dfs(arr, 0, list, ans);

        System.out.println(JSON.toJSONString(ans));
    }





    public static void dfs(int[] arr, int index, List<Integer> list, List<List<Integer>> ans){
        if(index >= arr.length){
            return;
        }
        list = new ArrayList<>(list);
        ans.add(list);
        //决策1 不添加当前元素
        dfs(arr, index+1, list, ans);

        //决策2 添加当前元素
        list.add(arr[index]);
        dfs(arr, index+1, list, ans);
    }


    public static void main(String[] args) {
        int[] arr = {1,2,2};
        List<Integer> list = new ArrayList<>();
        Set<List<Integer>> ans = new HashSet<>();
        Arrays.sort(arr);
        backTracing(arr, 0, list, ans);
        System.out.println(JSON.toJSONString(ans));
        new ArrayList<>(ans);
    }


    public static void backTracing(int[] nums, int index, List<Integer> list, Set<List<Integer>> ans){

        //边界条件
        if(index == nums.length){
            ans.add(new ArrayList<>(list));
            return;
        }

        //决策1， 选中当前元素
        list.add(nums[index]);
        backTracing(nums, index+1, list, ans);

        //决策2， 不选择当前元素
        list.remove(list.size()-1);
        backTracing(nums, index+1, list, ans);

    }
}
